package mo.daliy;

import java.util.*;

public class L886 {

    public boolean possibleBipartition(int n, int[][] dislikes) {
        if (dislikes.length <= 0) {
            return true;
        }
        int[] color = new int[n+1];
        List<Integer>[] graph = new List[n+1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] pair : dislikes) {
            graph[pair[0]].add(pair[1]);
            graph[pair[1]].add(pair[0]);
        }
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && !dfs(color, i, 1, graph)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int[] color, int cur, int value, List<Integer>[] graph) {
        color[cur] = value;
        List<Integer> dislikes = graph[cur];
        for (Integer next : dislikes) {
            if (color[next] == value) {
                return false;
            }
            if (color[next] == 0 && !dfs(color, next, 3 ^ value, graph)) {
                return false;
            }
        }
        return true;
    }

}
